package 栈;

/**
 * @author: 大怪
 * @email: 962527441@qq.com
 */

import java.util.Stack;

/**
 * 题目：
 * 给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。
 * 注意：此题 matrix 输入格式为一维 01 字符串数组。
 *
 * 示例 1：
 * 输入：matrix = ["10100","10111","11111","10010"]
 * 输出：6
 * 解释：最大矩形如上图所示。
 */
public class 矩阵中最大的矩形 {
    class Solution {
        public int maximalRectangle(String[] matrix) {
            if(matrix.length == 0 || matrix[0].length()==0) {
                return 0;
            }
            int max = 0;
            int[] tmp = new int[matrix[0].length()];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < tmp.length; j++) {
                    if(matrix[i].charAt(j) == '0') {
                        tmp[j]=0;
                    }else {
                        tmp[j]++;
                    }
                }
                int tmax = test(tmp);
                max = Math.max(tmax, max);
            }
            return max;
        }

        public int test(int[] matrix) {
            Stack<Integer> stack = new Stack<Integer>();
            stack.push(-1);
            int max = 0;
            for (int i = 0; i < matrix.length; i++) {
                while(stack.peek() !=-1 &&matrix[stack.peek()] >= matrix[i]) {
                    int height = matrix[stack.pop()];
                    int width = i - stack.peek()-1;
                    max = Math.max(max, height * width);
                }
                stack.push(i);
            }
            while (stack.peek() != -1) {
                int height = matrix[stack.pop()];
                int width = matrix.length - stack.peek() - 1;
                max = Math.max(max, height * width);
            }
            return max;
        }
    }
}
